1. Field of the Invention
This invention relates to three-dimensional graphics, particularly to determining whether objects oriented in three dimensions but displayed in two dimensions overlap or interfere in the undisplayed dimension. Whether objects drawn in two dimensions overlap or interfere with one another in the two displayed dimensions can be visually verified. When the objects are oriented in three-dimensional space, interference is not discernible from the two-dimensional display. For example, in piping diagrams for architectural drawings, the pipes occupy three dimensions. As more pipes are added, it is necessary to know that one pipe does not interfere with a pipe that is already positioned.
2. Description of Related Art
The prior art method of ascertaining whether there is any interference between pairs of objects in three-dimensional drawings (two-dimensional layouts) depends on making two sets of drawings at the same time, each representing a different pair combination of the three-dimensional space, e.g., top and side views. This is difficult and time consuming, especially if many changes have to be made.
Another prior art method more adaptable to automated systems, i.e., computer-aided drafting (or design), known as CAD, is to calculate for each added object possible intersections with all the previous objects.
The mathematics for determining intersections of vectors are well known. For example, if the equations of two three-dimensional vectors have a simultaneous solution, then the vectors intersect at the coordinates represented by the simultaneous solution. Three-dimensional objects in space can be represented by combinations of vector equations and the intersection of any pair of vectors where one of the pairs is from one object and the other is from the other object reveals that the objects interfere with one another.
For objects that can be represented by combinations of polygons, the calculations for interference can be made by pair-wise determinations of the polygons of each pair of objects. An efficient algorithm for determining polygon intersections is described in Algorithms for Graphics and Image Processing by Theo Pavlidis (Computer Science Press 1982) at pages 352 to 355.
The number of calculations required increases rapidly as the number and complexity of the objects increase. For example, if the number of polygons for the i-th object is n(i) and there are m objects, the number of calculations (each requiring many arithmetical operations) is the sum of m products, each product being the number n(k) of each k-th object times the sum of all n(j) objects where j is one less than k.
Examples of the increase can be shown by noting that for three cubes (comprising six polygons each), 108 calculations would be required and the addition of a fourth cube increases the number to 216, double the number of calculations. For two cubes and two spheres (represented by dodecagons, i.e., twelve pentagons), the number of calculations is 468 and the addition of another sphere increases the figure to 900, almost double the number of calculations. Because the number of calculations increases with an increase in the number of polygons used to compose an object, the increase in time for making the calculations mitigates against using more complex but better represented objects.